#include <list>
#include <unordered_map>
#include <utility>

using namespace std;
class LRUCache {
private:
  // 存储数据
  list<pair<int, int>> _list;
  // 记录list中各个数据的位置
  unordered_map<int, list<pair<int, int>>::iterator> _map;
  // 缓存大小
  int _capacity;
  // 当前已存储数据量
  int _size;

private:
public:
  LRUCache(int capacity) : _capacity(capacity), _size(0) {}

  int get(int key) {
    // 获取当前数据
    auto iter = _map.find(key);
    // 该元素不存在
    if (iter == _map.end()) {
      return -1;
    }
    // 该元素位于链表头部，无需移动
    if (iter->second == _list.begin()) {
      return iter->second->second;
    }
    // 移动元素至头部
    pair<int, int> p = *iter->second;
    _list.erase(iter->second);
    _list.push_front(p);
    _map[key] = _list.begin();
    return p.second;
  }

  void put(int key, int value) {
    // 如果存在 更新值
    auto iter = _map.find(key);
    if (iter == _map.end()) {
      // 该数据不存在 在链表头部插入数据
      if (_size == _capacity) {
        // 链表满,删除最后一个元素,清除数据索引
        pair<int, int> t = _list.back();
        _list.pop_back();
        _map.erase(t.first);
        _size--;
      }
      _list.push_front({key, value});
      _map[key] = _list.begin();
      _size++;
    } else {
      // 数据存在
      auto t = *iter->second;
      // 更新数据
      t.second = value;
      _list.erase(iter->second);
      _list.push_front(t);
      _map[key] = _list.begin();
    }
  }
};

/**
["LRUCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
LRUCache 2

1,1
2,2 1,1
1,1 2,2
3,3 1,1
-1

*/